import java.util.*;

public class Leetcode {
}

//leetcode:733:图像渲染
class Solution1 {
    int[] dx = {0,0,1,-1};
    int[] dy = {1,-1,0,0};
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        int prev = image[sr][sc];
        if(prev == color) return image;

        int m = image.length, n = image[0].length;

        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{sr,sc});

        while(!q.isEmpty()){
            int[] t = q.poll();
            int a = t[0], b = t[1];
            image[a][b] = color;
            for(int k = 0; k < 4; k++){
                int x = a + dx[k], y = b + dy[k];
                if(x >= 0 && x < m && y >= 0 && y < n && image[x][y] == prev){
                    q.offer(new int[]{x,y});
                }
            }
        }
        return image;
    }
}

//leetcode:200:岛屿数量
class Solution2 {
    int[] dx = {0,0,1,-1};
    int[] dy = {1,-1,0,0};
    boolean[][] visits;
    public int numIslands(char[][] grid) {
        int m = grid.length, n = grid[0].length;
        visits = new boolean[m][n];
        int ret = 0;
        for (int i = 0; i < m ;i++) {
            for (int j = 0; j < n ;j++) {
                if (!visits[i][j] && grid[i][j] == '1') {
                    ret++;
                    visits[i][j] = true;
                    Queue<int[]> q = new LinkedList<>();
                    q.offer(new int[]{i,j});
                    while(!q.isEmpty()){
                        int[] s = q.poll();
                        int a = s[0], b = s[1];
                        for(int k = 0; k < 4; k++){
                            int x = a + dx[k], y = b + dy[k];
                            if(x >= 0 && x < m && y >= 0 && y < n && !visits[x][y] && grid[x][y] == '1' ){
                                q.offer(new int[]{x,y});
                                visits[x][y] = true;
                            }
                        }
                    }
                }
            }
        }
        return ret;
    }
}

//leetcode:695:岛屿的最大面积
class Solution3 {
    int[] dx = {0,0,1,-1};
    int[] dy = {1,-1,0,0};
    boolean[][] visits;
    public int maxAreaOfIsland(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        visits = new boolean[m][n];
        int ret = 0;
        for (int i = 0; i < m ; i++) {
            for (int j = 0; j < n ; j++) {
                if (!visits[i][j] && grid[i][j] == 1) {
                    int count = 1;
                    visits[i][j] = true;
                    Queue<int[]> q = new LinkedList<>();
                    q.offer(new int[]{i,j});
                    while (!q.isEmpty()) {
                        int[] s = q.poll();
                        int a = s[0], b = s[1];
                        for (int k = 0; k < 4 ;k++) {
                            int x = a + dx[k], y = b + dy[k];
                            if( x >= 0 && x < m && y >= 0 && y < n && !visits[x][y] && grid[x][y] == 1){
                                visits[x][y] = true;
                                q.offer(new int[]{x,y});
                                count++;
                            }
                        }
                    }
                    ret = Math.max(ret,count);
                }
            }
        }
        return ret;
    }
}

//leetcode:130:被围绕的区域
class Solution4 {
    int[] dx = {0,0,1,-1};
    int[] dy = {1,-1,0,0};
    boolean[][] visits;
    public void solve(char[][] board) {
        int m = board.length, n = board[0].length;
        visits = new boolean[m][n];
        Queue<int[]> q = new LinkedList<>();
        for (int i = 0; i < m ; i++) {
            if (board[i][0] == 'O') {
                visits[i][0] = true;
                q.offer(new int[]{i,0});
                board[i][0] = '.';
            }
            if (board[i][n-1] == 'O') {
                visits[i][n-1] = true;
                q.offer(new int[]{i,n-1});
                board[i][n-1] = '.';
            }
        }

        for (int i = 1; i < n-1 ; i++) {
            if (board[0][i] == 'O') {
                visits[0][i] = true;
                q.offer(new int[]{0,i});
                board[0][i] = '.';
            }
            if (board[m-1][i] == 'O') {
                visits[m-1][i] = true;
                q.offer(new int[]{m-1,i});
                board[m-1][i] = '.';
            }
        }

        while (!q.isEmpty()) {
            int[] s = q.poll();
            int a = s[0], b = s[1];
            for (int k = 0; k < 4 ; k++) {
                int x = a + dx[k], y = b + dy[k];
                if (x >= 0 && x < m && y >= 0 && y < n && !visits[x][y] && board[x][y] == 'O') {
                    visits[x][y] = true;
                    q.offer(new int[]{x,y});
                    board[x][y] = '.';
                }
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n ; j++) {
                if (board[i][j] == '.') {
                    board[i][j] = 'O';
                }else if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }
    }
}